package com.dyz.leetcode._01_array;

public class _1370_sortString {
    //时间复杂度 26*m--> m为的长度
    public String sortString(String s) {
        StringBuilder res = new StringBuilder();

        int len = s.length();
        int[] freq = new int[26];

        for(int i=0; i<len; i++){
            char c = s.charAt(i);
            freq[c-'a']++;
        }

        for(int i=0; i<len; ){
            //上升
            for(int start=0; start<26; start++){
                if(freq[start]>0){
                    res.append((char)(start+'a'));
                    freq[start]--;
                    i++;
                }
            }

            //下降
            for(int end=25; end>=0; end--){
                if(freq[end]>0){
                    res.append((char)(end+'a'));
                    freq[end]--;
                    i++;
                }
            }
        }
        return res.toString();
    }
}
